package Leetcode.ArrayAndLinkedList.detectCycle142;

/**
 * 快慢指针法先记录下两者相遇的位置
 * 再从起始位置和相遇位置分别相同速度遍历
 * 相遇的位置即第一个节点位置
 */

/**
 * 次数 2
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        //快慢指针初始位置应该相同 类比龟兔赛跑
        ListNode meet = null;
        while (fast != null && fast.next != null && fast.next.next != null) {
            //先让快慢指针跑起来再比较
            slow = slow.next;
            fast = fast.next.next;
            if (fast.equals(slow)) {
                meet = fast;
                break;
            }
        }

        if(meet != null) {
            while(meet != null) {
                //先比较再跑
                if(meet.equals(head)) {
                    return meet;
                }
                meet = meet.next;
                head = head.next;

            }
        }

        return meet;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node1;
        Solution solution = new Solution();
        System.out.println(solution.detectCycle(head));
    }
}









/**
 *  public ListNode detectCycle(ListNode head) {
 *         if(head == null) {
 *             return null;
 *         }
 *         ListNode fast = head;
 *         ListNode slow = head;
 *         ListNode meet = null;
 *         while(fast != null && fast.next !=null && fast.next.next != null) {
 *             fast = fast.next.next;
 *             slow = slow.next;
 *             if(fast.equals(slow)) {
 *                 meet = fast;
 *                break;
 *             }
 *         }
 *         if(meet != null) {
 *             while(meet != null) {
 *                 if(head.equals(meet)) {
 *                     return meet;
 *                 }
 *                 head = head.next;
 *                 meet = meet.next;
 *             }
 *         }
 *         return null;
 *     }
 */
